/**
 * https://leetcode-cn.com/problems/merge-intervals/
 * 
 * 合并区间
 * @param intervals 
 */
const mergeInterval = (intervals: number[][]): number[][] => {
    const len = intervals.length;

    // 长度小于1, 直接返回intervals数组即可
    if (len <= 1) return intervals

    // 先排好序
    intervals.sort((a, b) => a[0] - b[0])

    // 创建新的数组
    const newArr: number[][] = [intervals[0]]

    for (let i = 1; i < len; i++) {
        const last = newArr[newArr.length - 1];
        if (last[1] >= intervals[i][0]) {
            // 找出较大的值, 替换掉first[1]
            last[1] = last[1] > intervals[i][1] ? last[1] : intervals[i][1]
        } else {
            // 不连续, 放入newArr中
            newArr.push(intervals[i])
        }
    }

    return newArr;
};




const mergeInterval2 = (intervals: number[][]): number[][] => {
    const len = intervals.length;

    /**
     * 堆排序
     * @param arr 
     */
    const hs = (arr: number[][]) => {
        let len = arr.length;
        // 数组元素小于2，不用排序
        if (len < 2) return;

        // 非叶子节点的结尾
        const e = (len >> 1) - 1;

        /**
         * 获取左孩子
         * @param i 
         */
        const getLeft = (i: number) => (i << 1) + 1;

        /**
         * 获取右孩子
         * @param i 
         */
        const getRight = (i: number) => (i << 1) + 2;

        /**
         * 获取左右孩子的最大值索引
         * @param l 
         * @param r 
         */
        const max = (l: number, r: number) => {
            if (r >= len) return l;
            const le = arr[l][0],
                re = arr[r][0];
            // 只有左孩子，没有右孩子 (交换元素下滤是，长度减一了，数组没变，可能导致r等于len是可以访问数组)     
            // 谁大返回谁的索引
            return le > re ? l : r
        }

        /**
         * 交换两个元素
         * @param l 
         * @param r 
         */
        const swap = (l: number, r: number) => {
            const tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }

        // 1. 原地建堆 (自底而上的下滤)
        const down = (i = 0) => {
            const sizes = len >> 1

            // sizes是非叶子节点的数量 (下滤只需要针对非叶子节点的数量)
            while (i < sizes) {
                let li = getLeft(i),
                    ri = getRight(i);
                // console.log(i, li, ri)
                // 1. 获取左右孩子的最大值
                const maxI = max(li, ri);
                // 2. 比较i位置和左右孩子的最大值
                // i比左右还大, 结束循环
                if (max(maxI, i) === i) {
                    break;
                }

                // i比左右孩子小, 交换位置
                // console.log(maxI, i)
                swap(maxI, i);

                // 更换i
                i = maxI;
            }
        }

        // 对非叶子节点进行下滤建堆
        for (let i = e; i >= 0; i--) {
            down(i)
        }


        // 2. 依次进行交换 (直到元素小于1为止)
        while (len > 1) {
            // 1. 第一个元素和最后一个元素交换位置 (len减1了，相当于不把最后一个元素算在内了)
            swap(0, --len)

            // 2. 对第一个元素进行下滤 (恢复堆的性质)
            down()
        }

    }


    // 长度小于1, 直接返回intervals数组即可
    if (len <= 1) return intervals

    // 创建新的数组
    const newArr: number[][] = []

    // 先排好序
    // intervals.sort((a, b) => a[0] - b[0])
    hs(intervals)
    console.log(intervals)
    // 将第一个
    let first = intervals[0]
    newArr.push(first)


    for (let i = 1; i < len; i++) {
        const last = newArr[newArr.length - 1];
        if (last[1] < intervals[i][0]) {
            // 不连续, 放入newArr中
            newArr.push(intervals[i])

            // 更新右边值
            // first[1] = intervals[i][1]
        } else {
            // 找出最小的, 替换掉first[0]
            // 找出较大的值, 替换掉first[1]
            last[1] = Math.max(last[1], intervals[i][1])
        }
    }

    return newArr;

};

// const arr3 = [[2, 3], [2, 2], [3, 3], [1, 3], [5, 7], [2, 2], [4, 6]]
// const arr3 = [[1, 4], [0, 1]]
const arr3 = [[4, 5], [2, 4], [4, 6], [3, 4], [0, 0], [1, 1], [3, 5], [2, 2]]
// const arr3 = [[1,4],[2,3]]
// const arr3 = [[1, 4], [1, 4]]
// const arr3 = [[1, 4], [4, 5]]
// const arr3 = [[1, 3], [2, 6], [8, 10], [15, 18]]
console.log(mergeInterval(arr3))